package leetcode;

import java.util.*;

public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> lists = threeSum(nums);
        String s1 = Arrays.toString(lists.toArray());
        System.out.println(s1);
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums == null || nums.length <= 2) return lists;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i]>0) break;
            if (i>0 && nums[i-1] == nums[i]) continue;
            int target = -nums[i];
            int left = i +1;
            int right = nums.length - 1;
            while (left<right){
                if (target == nums[left] + nums[right]){
                    lists.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    while (left<right && nums[left] == nums[left -1]) left++;
                    while (left<right && nums[right+1] == nums[right]) right--;
                }else if (target > nums[left] + nums[right]){
                    left++;
                }else {
                    right--;
                }
            }
        }
        return lists;
    }
}
